{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find a Corresponding Node of a Binary Tree in a Clone of That Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getTargetCopy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出克隆二叉树中的相同节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两棵二叉树，原始树 <code>original</code> 和克隆树 <code>cloned</code>，以及一个位于原始树 <code>original</code>&nbsp;中的目标节点&nbsp;<code>target</code>。</p>\n",
    "\n",
    "<p>其中，克隆树 <code>cloned</code>&nbsp;是原始树 <code>original</code>&nbsp;的一个<strong> 副本 </strong>。</p>\n",
    "\n",
    "<p>请找出在树&nbsp;<code>cloned</code>&nbsp;中，与&nbsp;<code>target</code>&nbsp;<strong>相同&nbsp;</strong>的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>你 <strong>不能</strong> 对两棵二叉树，以及 <code>target</code>&nbsp;节点进行更改。<strong>只能</strong> 返回对克隆树&nbsp;<code>cloned</code>&nbsp;中已有的节点的引用。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/21/e1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> tree = [7,4,3,null,null,6,19], target = 3\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/21/e2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> tree = [7], target =  7\n",
    "<strong>输出:</strong> 7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/21/e3.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数量范围为<meta charset=\"UTF-8\" />&nbsp;<code>[1, 10<sup>4</sup>]</code>&nbsp;。</li>\n",
    "\t<li>同一棵树中，没有值相同的节点。</li>\n",
    "\t<li><code>target</code>&nbsp;节点是树&nbsp;<code>original</code>&nbsp;中的一个节点，并且不会是&nbsp;<code>null</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果树中允许出现值相同的节点，将如何解答？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree](https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree](https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,4,3,null,null,6,19]\\n3', '[7]\\n7', '[8,null,6,null,5,null,4,null,3,null,2,null,1]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def traversal(root, target):\n",
    "            if not root: return None\n",
    "            if root.val == target.val:\n",
    "                return root\n",
    "            return traversal(root.left, target) or traversal(root.right, target)\n",
    "            # traversal(root.right, target)\n",
    "        return traversal(cloned, target)\n",
    "        # def helper(node):\n",
    "        #     if not node:\n",
    "        #         return None\n",
    "        #     if node.val==target.val:\n",
    "        #         self.res=node\n",
    "        #     helper(node.left) \n",
    "        #     helper(node.right)\n",
    "        # helper(cloned)\n",
    "        # return self.res\n",
    " \n",
    "        # def traversal(root, target):\n",
    "        #     if not root: return None\n",
    "        #     print('root.val', root.val)\n",
    "        #     print('target', target)\n",
    "        #     # if str(root) == str(target):\n",
    "        #     if root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right):\n",
    "        #         return root\n",
    "        #     # return root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right)\n",
    "        #     # return root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right)\n",
    "        #     # if root.val == target.val and root.left == target.left and root.right == target.right:\n",
    "        #         # return root\n",
    "            \n",
    "        #         # if not traversal(root.left) return traversal(root.left) else traversal(root.right)\n",
    "        #     # return traversal(root.left, target) if traversal(root.left, target) else traversal(root.right, target)\n",
    "        # return traversal(cloned, target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def go(tn: TreeNode) -> TreeNode | None:\n",
    "            if tn is None:\n",
    "                return None\n",
    "            if tn.val == target.val:\n",
    "                return tn\n",
    "            else:\n",
    "                return go(tn.left) or go(tn.right)\n",
    "\n",
    "        return go(cloned)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "        def dfs(node, cloned):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node == target:\n",
    "                self.res = cloned\n",
    "            dfs(node.left, cloned.left)\n",
    "            dfs(node.right, cloned.right)\n",
    "        dfs(original, cloned)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        # 进阶题解 - 双重DFS\n",
    "        def check(node, target):\n",
    "            if node.val != target.val: return False\n",
    "            if node.left and target.left: L =  check(node.left, target.left)\n",
    "            else: return False\n",
    "            if node.right and target.right: R = check(node.right, target.right)\n",
    "            else: return False\n",
    "            return L and R\n",
    "        queue = deque()\n",
    "        queue.append(cloned)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if check(node, target):\n",
    "                return node \n",
    "            if node.left: queue.append(node.left)\n",
    "            if node.right: queue.append(node.right)\n",
    "\n",
    "        # 基本题解 - BFS+节点值判断\n",
    "        queue = deque()\n",
    "        queue.append(cloned)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.val == target.val:\n",
    "                return node\n",
    "            if node.left: queue.append(node.left)\n",
    "            if node.right: queue.append(node.right)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def getTarget(root, target):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == target.val:\n",
    "                self.res = root\n",
    "                return\n",
    "            getTarget(root.left, target) \n",
    "            getTarget(root.right, target)\n",
    "        self.res = TreeNode()\n",
    "        getTarget(cloned, target)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        stack = [cloned]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.val == target.val:\n",
    "                return node\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def dfs(node=cloned):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val==target.val:\n",
    "                self.ans=node\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs()\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = None\n",
    "\n",
    "    def getTarget(self, root: TreeNode, target: TreeNode):\n",
    "        if not root:\n",
    "            return []\n",
    "        if root.val == target.val:\n",
    "            self.result = root\n",
    "            return self.result\n",
    "        self.getTarget(root.left, target)\n",
    "        self.getTarget(root.right, target)\n",
    "\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.getTarget(cloned, target)       \n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.res = None;\n",
    "        def dfs(cl,ta):\n",
    "            if(cl.val == ta.val):\n",
    "                self.res = cl;\n",
    "            if(cl.left != None):\n",
    "                dfs(cl.left,ta);\n",
    "            if(cl.right != None):\n",
    "                dfs(cl.right,ta);\n",
    "\n",
    "        dfs(cloned,target);\n",
    "        return self.res;\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = None\n",
    "\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode,\n",
    "                      target: TreeNode) -> TreeNode:\n",
    "        if original is None or cloned is None:\n",
    "            return self.res\n",
    "        self.getRes(cloned, target)\n",
    "        return self.res\n",
    "\n",
    "    def getRes(self, node: TreeNode, target: TreeNode) -> None:\n",
    "        if node is None:\n",
    "            return\n",
    "        if node.val == target.val:\n",
    "            self.res = node\n",
    "            return\n",
    "        self.getRes(node.left, target)\n",
    "        self.getRes(node.right, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node:\n",
    "                if node.val == target.val:\n",
    "                    ans = node\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(cloned)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        stack = [cloned]\n",
    "        while stack:\n",
    "            p = stack.pop(0)\n",
    "            if p.val == target.val:\n",
    "                return p\n",
    "            if p.left:\n",
    "                stack.append(p.left)\n",
    "            if p.right:\n",
    "                stack.append(p.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.node = ListNode()\n",
    "        def preorder(tree):\n",
    "            if not tree: return\n",
    "            if tree.val == target.val:\n",
    "                self.node = tree\n",
    "                return self.node\n",
    "            preorder(tree.left)\n",
    "            preorder(tree.right)\n",
    "        preorder(cloned)\n",
    "        return self.node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def helper(node, target):\n",
    "            if not node or node.val == target.val:\n",
    "                return node\n",
    "            return helper(node.left, target) or helper(node.right, target)\n",
    "        return helper(cloned, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if not cloned:\n",
    "            return\n",
    "        if cloned.val == target.val:\n",
    "            return cloned\n",
    "        return self.getTargetCopy(original, cloned.left, target) or self.getTargetCopy(original, cloned.right, target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        def dfs(root, target):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val==target.val:\n",
    "                nonlocal ans\n",
    "                ans = root\n",
    "            else:\n",
    "                dfs(root.left, target)\n",
    "                dfs(root.right, target)\n",
    "        dfs(cloned,target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "\n",
    "        def bfs(node, clone_node):\n",
    "            # print (node.val, clone_node.val)\n",
    "            if node == target:\n",
    "                return clone_node\n",
    "\n",
    "            if node.left:\n",
    "                result = bfs(node.left, clone_node.left)\n",
    "                if result:\n",
    "                    return result\n",
    "\n",
    "            if node.right:\n",
    "                result = bfs(node.right, clone_node.right)\n",
    "                if result:\n",
    "                    return result\n",
    "\n",
    "            return None\n",
    "\n",
    "        return bfs(original, cloned)\n",
    "\n",
    "\n",
    "        # morris \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.res = None\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val == target.val:\n",
    "                self.res = node\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            pass\n",
    "        \n",
    "        dfs(cloned)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        q=[]\n",
    "        q.append(cloned)\n",
    "        while q:\n",
    "            a=q.pop()            \n",
    "            if a.val==target.val:\n",
    "                return a\n",
    "            if a.left:\n",
    "                q.append(a.left)                \n",
    "            if a.right:\n",
    "                q.append(a.right)                                    \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def dg(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val == target.val:\n",
    "                self.num = root\n",
    "            dg(root.left)\n",
    "            dg(root.right)\n",
    "            # return self.num\n",
    "        dg(cloned)\n",
    "        return self.num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        root=cloned\n",
    "        q=[]\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            a=q.pop()            \n",
    "            if a and a.val==target.val:\n",
    "                return a\n",
    "            if a and a.left:\n",
    "                q.append(a.left)                \n",
    "            if a and a.right:\n",
    "                q.append(a.right)                                    \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def getTarget(root, target):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.val == target.val:\n",
    "                return root\n",
    "            return getTarget(root.left, target) or getTarget(root.right, target)\n",
    "        return getTarget(cloned, target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        def t(r):\n",
    "            if not r:\n",
    "                return\n",
    "            t(r.left)\n",
    "            nonlocal ans\n",
    "            if r.val == target.val:\n",
    "                ans=r\n",
    "            t(r.right)\n",
    "        t(cloned)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\r\n",
    "        if not original: return None\r\n",
    "        if original == target: return cloned\r\n",
    "        return self.getTargetCopy(original.left, cloned.left, target) or self.getTargetCopy(original.right, cloned.right, target)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        found = TreeNode() #初始化该点\n",
    "        def pre(tree):\n",
    "            nonlocal found\n",
    "            if tree == None:\n",
    "                return \n",
    "            if tree.val == target.val:#有一样的\n",
    "                found = tree\n",
    "                return\n",
    "            pre(tree.left)\n",
    "            pre(tree.right)\n",
    "        pre(cloned)\n",
    "        return found\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def dfs(node,target):\n",
    "            if not node:return None\n",
    "            if node.val==target.val:\n",
    "                return node\n",
    "            # if node.left:\n",
    "            #     return dfs(node.left,target)\n",
    "            # if node.right:\n",
    "            #     return dfs(node.right,target)\n",
    "            # return None\n",
    "            left=dfs(node.left,target)\n",
    "            if left and left.val==target.val:\n",
    "                return left\n",
    "            right=dfs(node.right,target)\n",
    "            if right and right.val==target.val:\n",
    "                return right\n",
    "            return None\n",
    "        return dfs(cloned,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val==target.val:\n",
    "                self.res=node\n",
    "            helper(node.left) \n",
    "            helper(node.right)\n",
    "        helper(cloned)\n",
    "        return self.res\n",
    " \n",
    "        # def traversal(root, target):\n",
    "        #     if not root: return None\n",
    "        #     print('root.val', root.val)\n",
    "        #     print('target', target)\n",
    "        #     # if str(root) == str(target):\n",
    "        #     if root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right):\n",
    "        #         return root\n",
    "        #     # return root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right)\n",
    "        #     # return root.val == target.val and traversal(root.left, target.left) and traversal(root.right, target.right)\n",
    "        #     # if root.val == target.val and root.left == target.left and root.right == target.right:\n",
    "        #         # return root\n",
    "            \n",
    "        #         # if not traversal(root.left) return traversal(root.left) else traversal(root.right)\n",
    "        #     # return traversal(root.left, target) if traversal(root.left, target) else traversal(root.right, target)\n",
    "        # return traversal(cloned, target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        return self.bfs(cloned, target)\n",
    "    \n",
    "    def bfs(self, root: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            temp = queue.pop(0)\n",
    "            if temp.val == target.val:\n",
    "                return temp\n",
    "            if temp.left:\n",
    "                queue.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue.append(temp.right)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = {}\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            dic[root.val] = root\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(cloned)\n",
    "        return dic[target.val]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "### my:DFS-pass\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def dfs(node,target):\n",
    "            if not node:return None\n",
    "            if node.val==target.val:\n",
    "                return node\n",
    "            # if node.left:\n",
    "            #     return dfs(node.left,target)\n",
    "            # if node.right:\n",
    "            #     return dfs(node.right,target)\n",
    "            # return None\n",
    "            left=dfs(node.left,target)\n",
    "            if left and left.val==target.val:\n",
    "                return left\n",
    "            right=dfs(node.right,target)\n",
    "            if right and right.val==target.val:\n",
    "                return right\n",
    "            return None\n",
    "        return dfs(cloned,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        q = deque([cloned])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.val == target.val:\n",
    "                return node\n",
    "            if node.left: q.append(node.left)\n",
    "            if node.right: q.append(node.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.ans = TreeNode(0)\n",
    "        self.flag = False\n",
    "        def dfs(node1: TreeNode, node2: TreeNode):\n",
    "            if self.flag:\n",
    "                return \n",
    "            if node1 == target:\n",
    "                self.ans = node2\n",
    "                self.flag = True\n",
    "                return\n",
    "            if node1.left:\n",
    "                dfs(node1.left, node2.left)\n",
    "            if node1.right:\n",
    "                dfs(node1.right, node2.right)\n",
    "        \n",
    "        dfs(original, cloned)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val == target.val:\n",
    "                self.res=node\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "        helper(cloned)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        queue1, queue2 = deque(), deque()\n",
    "        queue1.append(original)\n",
    "        queue2.append(cloned)\n",
    "        while queue1:\n",
    "            n = len(queue1)\n",
    "            for i in range(n):\n",
    "                node1 = queue1.popleft()\n",
    "                node2 = queue2.popleft()\n",
    "                if node1 == target:\n",
    "                    return node2\n",
    "                if node1.left:\n",
    "                    queue1.append(node1.left)\n",
    "                    queue2.append(node2.left)\n",
    "                if node2.right:\n",
    "                    queue1.append(node1.right)\n",
    "                    queue2.append(node2.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.ans = TreeNode(0)\n",
    "        def dfs(node1: TreeNode, node2: TreeNode):\n",
    "            if node1 == target:\n",
    "                self.ans = node2\n",
    "                return\n",
    "            if node1.left:\n",
    "                dfs(node1.left, node2.left)\n",
    "            if node1.right:\n",
    "                dfs(node1.right, node2.right)\n",
    "        \n",
    "        dfs(original, cloned)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        tv=target.val\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val==tv:\n",
    "                    return root\n",
    "                lr,rr=dfs(root.left),dfs(root.right)\n",
    "                return lr if lr else rr\n",
    "            return None\n",
    "        return dfs(cloned)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if not original:\n",
    "            return\n",
    "        if original == target:\n",
    "            return cloned\n",
    "        ans = self.getTargetCopy(original.left, cloned.left, target)\n",
    "        if ans:\n",
    "            return ans\n",
    "        ans = self.getTargetCopy(original.right, cloned.right, target)\n",
    "        if ans:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = dict()\n",
    "        def preorder(cloned):\n",
    "            if not cloned:\n",
    "                return\n",
    "            dic[cloned.val] = cloned\n",
    "            preorder(cloned.left)\n",
    "            preorder(cloned.right)\n",
    "        preorder(cloned)\n",
    "        return dic[target.val]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        stack = [cloned]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.val == target.val:\n",
    "                return node\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if not original:return None\n",
    "        if original==target:return cloned\n",
    "        l=self.getTargetCopy(original.left,cloned.left,target)\n",
    "        if l:return l\n",
    "        r=self.getTargetCopy(original.right,cloned.right,target)\n",
    "        if r:return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        def getRoot(root):\n",
    "            if root:\n",
    "                if root.val == target.val:\n",
    "                    self.result = root\n",
    "                getRoot(root.left)\n",
    "                getRoot(root.right)\n",
    "        getRoot(cloned)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "         \n",
    "        def getRes(root):\n",
    "            nonlocal target\n",
    "            if root == None or root.val == target.val:\n",
    "                 return root\n",
    "            left = getRes(root.left)\n",
    "            right = getRes(root.right)\n",
    "            if left != None and right == None:\n",
    "                return left\n",
    "            if right == None and left == None:\n",
    "                return None\n",
    "            if left == None and right != None:\n",
    "                return right\n",
    "            if left != None and right != None:\n",
    "                return left\n",
    "        \n",
    "        return getRes(cloned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if cloned == None:\n",
    "            return None\n",
    "        if cloned.val == target.val:\n",
    "            return cloned\n",
    "        else:\n",
    "            return self.getTargetCopy(original, cloned.left, target) or self.getTargetCopy(original, cloned.right, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        found = TreeNode() #初始化该点\n",
    "        def pre(tree):\n",
    "            nonlocal found\n",
    "            if tree == None:\n",
    "                return \n",
    "            if tree.val == target.val:#有一样的\n",
    "                found = tree\n",
    "                return\n",
    "            pre(tree.left)\n",
    "            pre(tree.right)\n",
    "        pre(cloned)\n",
    "        return found\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.node = TreeNode()\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.dbs(cloned, target)\n",
    "        return self.node\n",
    "    \n",
    "    def dbs(self, root, target: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        if root.val == target.val:\n",
    "            self.node = root\n",
    "            return\n",
    "        else:\n",
    "            self.dbs(root.left, target)\n",
    "            self.dbs(root.right, target)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import copy\n",
    "class Solution:\n",
    "    def dfs_to_find(self, root, path):\n",
    "        if not root: return\n",
    "        if root == self.target:\n",
    "            self.path = copy.deepcopy(path)\n",
    "            return\n",
    "        path.append('l')\n",
    "        self.dfs_to_find(root.left, path)\n",
    "        path.pop()\n",
    "        path.append('r')\n",
    "        self.dfs_to_find(root.right, path)\n",
    "        path.pop()\n",
    "    \n",
    "\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        self.target = target\n",
    "        self.path = []\n",
    "        self.dfs_to_find(original, [])\n",
    "        if not self.path: return cloned\n",
    "        while(len(self.path)):\n",
    "            top = self.path.pop(0)\n",
    "            if top == 'l':\n",
    "                cloned = cloned.left\n",
    "            else:\n",
    "                cloned = cloned.right\n",
    "        return cloned\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.val == target.val:\n",
    "                res.append(root)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(cloned)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        \n",
    "        ret = []\n",
    "        # print(target)\n",
    "        # print(target.val)\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return\n",
    "\n",
    "           # print(root.val)\n",
    "            if root.val == target.val:\n",
    "                ret.append(root)\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(cloned)\n",
    "        return ret[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-            \n",
    "# @Time : 2023/10/1 23:25\n",
    "# @Author:yhq\n",
    "# @FileName: LC_广搜_1379. 找出克隆二叉树中的相同节点.py\n",
    "# @Software: 2023 Python 编程能力提升专项\n",
    "import time\n",
    "from typing import List\n",
    "from collections import  deque\n",
    "\n",
    "debug = True\n",
    "'''\n",
    "题目描述:\n",
    "'''\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def layerorder(self, tree):\n",
    "        '''\n",
    "        二叉树层序遍历方法 遍历顺序：\n",
    "        1、当前值是否满足,满足则退出\n",
    "        2、不满足，则把它的子节点也加入队列中\n",
    "        3、退出条件：没有左节点也没有右节点；\n",
    "        :param tree:传入的树结构\n",
    "        :return:\n",
    "        '''\n",
    "        dq = deque([tree])\n",
    "        while dq:\n",
    "            item = dq.popleft()\n",
    "            if item.val == self.target_node.val:\n",
    "                self.founded_node=item\n",
    "                return  self.founded_node\n",
    "            \n",
    "            if not item.right and not item.left:\n",
    "                print(item.val, \" 是叶子节点，没有左右子树\")\n",
    "                continue\n",
    "\n",
    "            if item.right:\n",
    "                dq.append(item.right)\n",
    "            if item.left:\n",
    "                dq.append(item.left)\n",
    "        return  self.founded_node\n",
    "\n",
    "\n",
    "\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        '''\n",
    "        方法一：前序遍历方式实现\n",
    "        :param original:\n",
    "        :param cloned:\n",
    "        :param target:\n",
    "        :return:\n",
    "        '''\n",
    "        self.founded_node = TreeNode()\n",
    "        self.target_node = target\n",
    "        self.layerorder(cloned)\n",
    "        return self.founded_node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        ans = None\n",
    "        def dfs(l: TreeNode, r: TreeNode):\n",
    "            nonlocal ans\n",
    "            if not l:\n",
    "                return\n",
    "            if l == target:\n",
    "                ans = r\n",
    "                return\n",
    "            dfs(l.left, r.left)\n",
    "            dfs(l.right, r.right)\n",
    "        dfs(original, cloned)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = dict()\n",
    "        def preorder(cloned):\n",
    "            if not cloned:\n",
    "                return\n",
    "            dic[cloned.val] = cloned\n",
    "            preorder(cloned.left)\n",
    "            preorder(cloned.right)\n",
    "        preorder(cloned)\n",
    "        return dic[target.val]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = dict()\n",
    "        def preorder(cloned):\n",
    "            if not cloned:\n",
    "                return \n",
    "            dic[cloned.val] = cloned\n",
    "            preorder(cloned.left)\n",
    "            preorder(cloned.right)\n",
    "        preorder(cloned)\n",
    "        return dic[target.val]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = dict()\n",
    "        def preorder(cloned):\n",
    "            if not cloned:\n",
    "                return\n",
    "            dic[cloned.val] = cloned\n",
    "            preorder(cloned.left)\n",
    "            preorder(cloned.right)\n",
    "        preorder(cloned)\n",
    "        return dic[target.val]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if not original: return None \n",
    "        if original == target: return cloned\n",
    "        l = self.getTargetCopy(original.left, cloned.left, target)\n",
    "        r = self.getTargetCopy(original.right, cloned.right, target)\n",
    "        if not l and not r: return None \n",
    "        if l: return l \n",
    "        if r: return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        _stk = []\n",
    "        _stk.append(cloned)\n",
    "        while _stk:\n",
    "            node = _stk.pop()\n",
    "            if node.val == target.val:\n",
    "                return node\n",
    "            if node.left:\n",
    "                _stk.append(node.left)\n",
    "            if node.right:\n",
    "                _stk.append(node.right)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        if not original:return None\n",
    "        if original==target:return cloned\n",
    "        left=self.getTargetCopy(original.left,cloned.left,target)\n",
    "        right=self.getTargetCopy(original.right,cloned.right,target)\n",
    "        if left:return left\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\r\n",
    "        def trans(node, fn_v):\r\n",
    "            fn_v(node)\r\n",
    "            if node.left: trans(node.left,fn_v)\r\n",
    "            if node.right: trans(node.right,fn_v)\r\n",
    "        res = [None]\r\n",
    "        def transfn(v):\r\n",
    "            print('iter', v.val)\r\n",
    "            if v.val == target.val:\r\n",
    "                res[0] = v\r\n",
    "        trans(cloned, transfn)\r\n",
    "        print(res[0] and res[0].val or 'None')\r\n",
    "        return res[0]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        # 写一个广度优先搜索即可\n",
    "        before = [cloned]\n",
    "        while before:\n",
    "            after = []\n",
    "            for b in before:\n",
    "                if b.val == target.val:\n",
    "                    return b\n",
    "                else:\n",
    "                    if b.left:\n",
    "                        after.append(b.left)\n",
    "                    if b.right:\n",
    "                        after.append(b.right)\n",
    "            before = after"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:\n",
    "        dic = dict()\n",
    "        def preorder(cloned):\n",
    "            if not cloned:\n",
    "                return\n",
    "            dic[cloned.val] = cloned\n",
    "            preorder(cloned.left)\n",
    "            preorder(cloned.right)\n",
    "        preorder(cloned)\n",
    "        return dic[target.val]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
